package com.sicheng.lc.杂题.多路归并技巧之构造有序链表;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 17:11
 */
public class 找出第K小的数对距离 {
    //https://leetcode.cn/problems/find-k-th-smallest-pair-distance/


    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        System.out.println(n * (n - 1) / 2 - k);
        if (n * (n - 1) / 2 - k < (int) 1e4)
            return -1;
        PriorityQueue<int[]> heap = new PriorityQueue<>(n,
                Comparator.comparingInt(a -> Math.abs(nums[a[1]] - nums[a[0]])));

        for (int i = 0; i < n - 1; i++) {
            heap.offer(new int[]{i, i + 1});
        }
        int[] a = null;
        for (int i = 1; i <= k; i++) {
            if (heap.isEmpty())
                break;
            a = heap.poll();
            if (i == k)
                break;
            if (a[1] + 1 < n) {
                a[1]++;
                heap.offer(a);
            }
        }

        return Math.abs(nums[a[0]] - nums[a[1]]);
    }
}
